%% File Name: chSorting
%% Author: Anung B. Ariwibowo
%% History:
%%  2002.11.20: Start writing a template

\chapter{Sorting \label{ch:sorting}}

\section{Heap} \label{sect:heap} \index{\emph{Heap}}

Algoritma \emph{Heapsort} \index{\emph{Heap sort}} menggabungkan
keunggulan dari algoritma sorting \emph{merge} dan algoritma sorting
\emph{insertion}. Seperti \emph{mergesort} tetapi tidak seperti
\emph{insertionsort}, kompleksitas waktu \emph{heapsort} adalah \(O(n
      \lg n)\). Seperti \emph{insertionsort}, namun tidak seperti
\emph{mergesort}, \emph{heapsort} melakukan pengurutan terhadap data
masukan secara \emph{in place}: algoritma ini hanya memerlukan
struktur data yang besarnya selalu tetap di luar larik masukan.

Selain itu, algoritma \emph{heapsort} menggunakan sebuah struktur data yang disebut dengan \emph{heap}. \emph{Heap} dapat diimplementasikan dengan sebuah larik satu dimensi seperti digambarkan dalam Gambar~\ref{fig:heap}

Gambar~\ref{fig:heap} menunjukkan elemen-elemen yang disimpan dalam
sebuah larik (bagian bawah). Setiap elemen dalam larik bersesuaian
dengan setiap \emph{node} pada \emph{complete binary tree} (bagian
    atas). Setiap kali elemen baru ditambahkan ke dalam \emph{heap},
elemen tersebut ditambahkan ke bagian akhir dari larik, atau kalau
digambarkan dalam bentuk \emph{tree}, elemen baru tersebut akan
ditambahkan pada \emph{level} paling bawah mulai dari posisi paling
kiri yang masih kosong.

\begin{figure}
	\[
	\xygraph{
	  [] *++[o][F]{16}
    (-[dlll] *++[o][F]{14}
     (-[dll] *++[o][F]{8}
      (-[dl] *++[o][F]{2}
       , -[dr] *++[o][F]{4}
      )
      , -[drr] *++[o][F]{7}
      (-[dl] *++[o][F]{1}
      )
     )
     , -[drr] *++[o][F]{10}
     (-[dl] *++[o][F]{9}
      , -[dr] *++[o][F]{3}
    )
	}
	\]
  {\par\centering
  \includegraphics{heap-array}
  \par}
	\caption{Contoh Heap}
	\label{fig:heap}
\end{figure}

Karena disusun menggunakan \emph{complete binary tree}, setiap
\emph{node} dapat dengan mudah dicari \emph{parent},
\emph{left-child}, atau \emph{right-child}-nya.
Algoritma-algoritma~\ref{alg:heap-parent} sampai
dengan~\ref{alg:heap-right-child} memberikan cara menemukan
\emph{parent}, \emph{left-child}, dan \emph{right-child} dari sebuah
\emph{node} yang diberikan.

\begin{algorithm}
\begin{algorithmic}[1]
	\STATE \textsc{Parent} (i)
	\STATE return \(\left\lfloor i/2 \right\rfloor\)
\end{algorithmic}
\caption{Algoritma untuk mendapatkan parent dari sebuah
  node $i$ di dalam heap.} \label{alg:heap-parent}
\end{algorithm}

\begin{algorithm}
\begin{algorithmic}[1]
	\STATE \textsc{Left} (i)
	\STATE return \(2i\)
\end{algorithmic}
\caption{Algoritma untuk mendapatkan left-child dari sebuah
  node $i$ di dalam heap.} \label{alg:heap-left-child}
\end{algorithm}

\begin{algorithm}
\begin{algorithmic}[1]
	\STATE \textsc{Right} (i)
	\STATE return \(2i+1\)
\end{algorithmic}
\caption{Algoritma untuk mendapatkan right-child dari sebuah
  node $i$ di dalam heap.} \label{alg:heap-right-child}
\end{algorithm}

Setiap \emph{heap} memiliki sifat yang selalu terpenuhi untuk setiap
\emph{node} \(i\) di dalamnya:
\[
A[\textsc{Parent}(i)] \geq A[i] \ (\mathit{Heap Property})
\] \index{\emph{Heap Property}}
yaitu nilai dari setiap \emph{node} tidak mungkin melebihi nilai dari
\emph{parent}-nya. Karena adanya sifat ini, maka setiap \emph{heap}
akan menyimpan elemen terbesarnya pada \emph{root}.

\emph{\textbf{Height}} dari \emph{node} di dalam sebuah \emph{tree}
didefinisikan sebagai jumlah \emph{edge} terpanjang yang menghubungkan
\emph{node} tersebut dengan \emph{root}. Dalam pembahasan berikutnya
akan ditunjukkan bahwa semua operasi yang dilakukan terhadap
\emph{heap} (menyisipkan elemen baru, menghapus elemen, dsb)
  proporsional dengan \emph{height} dari \emph{tree} yang bersesuaian.
Sehingga semua operasi pada \emph{heap} memiliki
kompleksitas \(O(\lg n)\), dengan \(n\) adalah jumlah elemen yang
dimiliki oleh sebuah \emph{heap}.

Algoritma~\ref{alg:heapify} adalah algoritma utama dalam memanipulasi
sebuah \emph{heap}. Algoritma ini digunakan untuk menjaga agar
\emph{heap} selalu memenuhi \emph{Heap Property}. Masukan bagi
algoritma tersebut adalah sebuah larik \(A\) dan sebuah indeks \(i\).
Larik \(A\) adalah \emph{heap} yang sesungguhnya. \emph{Subtree} yang
dimulai dari \emph{node} \(i\) melanggar \emph{Heap Property}, karena
itu harus diatur sehingga \emph{subtree} tersebut kembali memenuhi
\emph{Heap Property}.

\emph{Subtree} yang \emph{root}-nya \textsc{Left}\(i\) dan
\textsc{Right}\(i\) sudah memenuhi \emph{Heap Property}, namun
nilai \(A[i]\) bernilai lebih kecil daripada kedua anaknya (atau anak
    kirinya saja), sehingga melanggar \emph{Heap Property}. Algoritma
\textsc{Heapify} menggeser \(A[i]\) ke bawah, sehingga \emph{subtree}
yang dimulai dari \(i\) kembali menjadi sebuah \emph{heap}.

\begin{algorithm}
\caption{\texttt{Heapify}} \index{\textsc{Heapify}}
\label{alg:heapify}
\begin{algorithmic}[1]
	\STATE \textsc{Heapify} \((A, i)\)
  \STATE \(l \leftarrow\) \textsc{Left} \((i)\)
  \STATE \(r \leftarrow\) \textsc{Right} \((i)\)
  \IF{\(l \leq \ \mathit{heap-size}[A]\) and \(A[l] > A[i]\)}
  	\STATE \(\mathit{largest} \ \leftarrow l\)
  \ELSE
  	\STATE \(\mathit{largest} \ \leftarrow i\)
  \ENDIF
  \IF{\(r \leq \ \mathit{heap-size}[A]\) and \(A[r] > A[\mathit{largest}]\)}
  	\STATE \(\mathit{largest} \ \leftarrow r\)
  \ENDIF
  \IF{\(\mathit{largest} \ \neq i\)}
  	\STATE swap \(A[i] \leftrightarrow A[largest]\)
  	\STATE \textsc{Heapify}\((A, \mathit{largest})\)
  \ENDIF
\end{algorithmic}
\end{algorithm}

\emph{Heap} \(A\) berikut ini tidak memenuhi \emph{Heap Property}:
\[
16 \ 4 \ 10 \ 14 \ 7 \ 9 \ 3 \ 2 \ 8 \ 1
\]
yaitu pada elemen ke-2. Anak kiri dari \emph{node} 2 adalah
\emph{node} 4, yang nilainya 14. Sedangkan anak kanannya adalah
\emph{node} 5, yang nilainya 7. Ketiga \emph{node} ini tidak memenuhi
\emph{Heap Property}. Agar \emph{heap} \(A\) kembali menjadi
\emph{heap} yang benar, algoritma \textsc{Heapify} digunakan:
\[
  \textsc{Heapify} (A, 2)
\]
Pada tahap pertama, 4 ditukar dengan 14, sehingga isi \emph{heap} pada
tahap ini adalah:
\[
16 \ 14 \ 10 \ 4 \ 7 \ 9 \ 3 \ 2 \ 8 \ 1
\]
Namun ini berarti \emph{subtree} pada \emph{node} 4 kembali melanggar
\emph{Heap Property}. Karena itu, secara rekursif, algoritma
\textsc{Heapify} kembali digunakan:
\[
  \textsc{Heapify} (A, 4)
\]
untuk mendapatkan \emph{heap} akhir yang sudah memenuhi \emph{Heap
  Property}:
\[
16 \ 14 \ 10 \ 8 \ 7 \ 9 \ 3 \ 2 \ 4 \ 1
\]


\subsection{Membangun Heap}

Algoritma \textsc{Heapify} dapat digunakan untuk membangun \emph{heap}
secara \emph{bottom-up}. Cara ini digambarkan dalam
Algoritma~\ref{alg:build-heap}. Masukan algoritma ini adalah sebuah
larik \(A\) yang berisi elemen-elemen yang akan dijadikan sebuah
\emph{heap}.

Elemen-elemen \(A[ ( \left\lfloor n/2 \right\rfloor + 1) . . n]\)
  adalah \emph{leaves} dari \emph{tree}, masing-masingnya dapat
  dianggap sebagai \emph{heap}-dengan-1-elemen. Ini artinya proses
  membangun \emph{heap} dapat dilakukan tanpa harus mengolah seluruh
  elemen dalam \(A\), cukup dimulai dari `pertengahan' larik saja,
  mundur sampai elemen pertama (yaitu \emph{root} dari \emph{tree}).

\begin{algorithm}
\caption{\texttt{Build-Heap}} \index{\textsc{Build-Heap}}
\label{alg:build-heap}
\begin{algorithmic}[1]
	\STATE \textsc{Build-Heap} (A)
	\STATE heap-size[A] \(\leftarrow\) length[A]
	\FOR{i \(\leftarrow \left\lfloor \mathrm{length[A]}/2 \right\rfloor\) downto \(1\)}
		\STATE \textsc{Heapify}(A,i)
	\ENDFOR
\end{algorithmic}
\end{algorithm}

Contoh larik berikut ini dapat digunakan untuk membangun sebuah
\emph{heap} dengan Algoritma~\ref{alg:build-heap}
\[
  4 \ 1 \ 3 \ 2 \ 16 \ 9 \ 10 \ 14 \ 8 \ 7
\]
Dalam setiap tahapan, langkah-langkah yang dilalui larik sampai
menjadi \emph{heap} adalah seperti ini:
\[
  \textsc{Heapify}(A,5): 4 \ 1 \ 3 \ 2 \ 16 \ 9 \ 10 \ 14 \ 8 \ 7
\]
\[
  \textsc{Heapify}(A,4): 4 \ 1 \ 3 \ 14 \ 16 \ 9 \ 10 \ 2 \ 8 \ 7
\]
\[
  \textsc{Heapify}(A,3): 4 \ 1 \ 10 \ 14 \ 16 \ 9 \ 3 \ 2 \ 8 \ 7
\]
\[
  \textsc{Heapify}(A,2): 4 \ 16 \ 10 \ 14 \ 7 \ 9 \ 3 \ 2 \ 8 \ 1
\]
\[
  \textsc{Heapify}(A,1): 16 \ 14 \ 10 \ 8 \ 7 \ 9 \ 3 \ 2 \ 4 \ 1
\]
Pada tahapan \textsc{Heapify}\((A,2)\), terdapat perpindahan \(A[2]\)
dengan \(A[5]\), dan kemudian dengan \(A[10]\). Pada tahapan
\textsc{Heapify}\((A,1)\) terdapat perpindahan \(A[1]\) dengan
\(A[2]\), dengan \(A[4]\), dan dengan \(A[9]\).


\section{Heapsort} \index{\emph{Heapsort}}

Sifat-sifat \emph{heap} bisa digunakan untuk mengurutkan data di dalam
sebuah larik. Algoritma~\ref{alg:heapsort} memberikan langkah-langkah
yang perlu dilakukan untuk mengurutkan sebuah larik \(A\) dengan
memanfaatkan \emph{Heap Property}.

Jika diberikan sebuah larik berisi data-data yang belum
terurut, langkah pertama yang harus dilakukan adalah mengubah larik
ini sehingga memenuhi \emph{Heap Property}. Setelah elemen-elemen di
dalam larik tersusun menjadi sebuah \emph{heap}, maka bisa dipastikan
elemen paling awal (\emph{root} dari \emph{tree}) adalah elemen dengan
nilai paling besar.

Untuk mengurutkan data, elemen-elemen di dalam
larik harus diurutkan mulai data dengan nilai terkecil sampai data
dengan nilai paling besar berada pada bagian akhir pada larik. Ketika
berada dalam kondisi \emph{heap}, larik menyimpan elemen dengan nilai
terbesar di elemen pertama. Maka yang perlu dilakukan adalah
menukarkan elemen pertama dengan elemen terakhir.

Setelah dilakukan pertukaran, ukuran \emph{heap} diperkecil, karena
elemen dengan nilai paling besar sudah `berada pada tempatnya',
tinggal \(n - 1\) elemen saja yang masih belum terurut dengan benar.
Karena telah dilakukan pertukaran tempat, maka \emph{heap} yang sudah
menjadi lebih kecil ukurannya ini tidak lagi memenuhi \emph{Heap
  Property}, karenanya larik ini perlu di-\emph{heapify} lagi untuk
menempatkan elemen terbesar di posisi \emph{root}. Berikutnya
dilakukan pertukaran tempat lagi antara elemen yang berada di
\emph{root} dengan elemen paling akhir di dalam \emph{heap}.

Perhatikan bahwa ukuran \emph{heap} sudah berkurang satu elemen dari
tahap sebelumnya, sehingga yang ditukarkan dengan elemen \emph{root}
adalah elemen yang berada satu tempat di depan elemen-elemen yang
sudah berada pada tempatnya secara terurut.

\begin{algorithm}
\caption{\texttt{Heapsort}} \index{\emph{Heapsort}}
\label{alg:heapsort}
\begin{algorithmic}[1]
	\STATE \textsc{Heapsort}(A)
	\STATE \textsc{Build-Heap} (A)
	\FOR{i \(\leftarrow\) length[A] downto \(2\)}
		\STATE swap A[1] \(\leftrightarrow\) A[i]
		\STATE heap-size[A] \(\leftarrow\) heap-size[A]-1
		\STATE \textsc{Heapify}(A,1)
	\ENDFOR
\end{algorithmic}
\end{algorithm}


\section{Counting Sort} \label{sect:counting-sort}
\index{\emph{Counting sort}}

\emph{\emph{Heap sort}} mengurutkan \(n\) buah data dengan cara kerja
membandingkan elemen-elemen data yang akan diurutkan. Beberapa jenis
algoritma sorting menggunakan teknik dasar ini juga, yaitu
membandingkan tiap elemen dari data yang akan diurutkan. Kelompok
algoritma yang menggunakan teknik sorting ini disebut
algoritma-algoritma \emph{\textbf{comparison sorts}}.
\index{\emph{comparison sorts}} Termasuk di dalam kelompok algoritma
ini antara lain \emph{Heap sort}, \emph{Merge sort}, dan \emph{Quick
  sort}.

Subbab~\ref{sect:counting-sort} dan~\ref{sect:radix-sort}
memperkenalkan dua algoritma pengurutan data -- \emph{counting sort}
dan \emph{radix sort} -- yang bekerja tanpa
menggunakan operasi dasar pembandingan semacam itu. Kedua algoritma
ini mengurutkan \(n\) data dengan kompleksitas waktu yang linier.

\emph{Counting sort} mengasumsikan untuk setiap \(n\) yang akan
diurutkan adalah bilangan-bilangan bulat yang berada pada rentang
nilai \(1\) sampai \(k\), untuk sembarang nilai \(k\). Ide dasar dari
algoritma sort ini adalah menentukan untuk setiap elemen \(x\) jumlah
elemen yang nilainya kurang dari \(x\). Informasi ini digunakan untuk
meletakkan \(x\) pada posisi yang benar. Misalkan ada 17 elemen yang
nilainya lebih kecil daripada \(x\), maka \(x\) harus ditempatkan pada
posisi ke-18. Ide ini harus dimodifikasi sedikit untuk mengatasi
keadaan di mana beberapa elemen memiliki nilai yang sama dengan \(x\),
untuk menghindari elemen-elemen yang nilainya sama ditempatkan pada
hanya satu posisi.

\begin{algorithm}
\caption{Algoritma Counting Sort} \label{alg:counting-sort}
\index{\emph{Counting sort}}
\begin{algorithmic}[1]
  \STATE \textsc{Counting-Sort} \( (A, B, k) \)
  \FOR{ \(i \leftarrow 1\) to \(k\) }
    \STATE \( C[i] \leftarrow 0 \)
  \ENDFOR
  \FOR{ \(j \leftarrow 1\) to \( \mathit{length}[A]\) }
    \STATE \(C[A[j]] \leftarrow C[A[j]] + 1 \)
  \ENDFOR
  \STATE \COMMENT{ \(C[i]\) sekarang berisi jumlah elemen yang sama
    dengan \(i\) }
  \FOR{ \( i \leftarrow 2 \) to \(k\) }
    \STATE \(C[i] \leftarrow C[i] + C[i-1] \)
  \ENDFOR
  \STATE \COMMENT{ \(C[i]\) sekarang berisi jumlah elemen yang kurang
    dari atau sama dengan \(i\) }
  \FOR{ \( j \leftarrow \mathit{length}[A] \) downto \(1\) }
    \STATE \( B[C[A[j]]] \leftarrow A[j] \)
    \STATE \( C[A[j]] \leftarrow C[A[j]] - 1 \)
  \ENDFOR
\end{algorithmic}
\end{algorithm}

Algoritma~\ref{alg:counting-sort} menerima masukan dalam larik \(A\)
yang berisi \(n\) elemen. Dalam pengerjaannya, algortima ini
membutuhkan dua larik lain: larik \(B\) digunakan untuk menyimpan
bilangan-bilangan yang telah terurut, dan larik \(C\) untuk menyimpan
bilangan-bilangan selama proses pengurutan dilakukan. Larik \(C\) ini
hanya bersifat temporer.

\begin{figure}
{\par\centering
\noindent \subfigure[]{\scalebox{0.9}{\includegraphics{count-sort-illus-1}}
\label{subfig:counting-sort-illustration-1}} %\goodgap
\subfigure[]{\scalebox{0.9}{\includegraphics{count-sort-illus-2}}
\label{subfig:counting-sort-illustration-2}} \\
\subfigure[]{\scalebox{0.9}{\includegraphics{count-sort-illus-3}}
\label{subfig:counting-sort-illustration-3}} %\goodgap
\subfigure[]{\scalebox{0.9}{\includegraphics{count-sort-illus-4}}
\label{subfig:counting-sort-illustration-4}} \\
\subfigure[]{\scalebox{0.9}{\includegraphics{count-sort-illus-5}}
\label{subfig:counting-sort-illustration-5}} %\goodgap
\subfigure[]{\scalebox{0.9}{\includegraphics{count-sort-illus-6}}
\label{subfig:counting-sort-illustration-6}} \\
\par}
%\caption[Contoh Counting sort]{Contoh Counting-Sort ketika beraksi pada larik $A[1..8]$ dengan tiap elemen $A$ adalah bilangan bulat yang tidak lebih dari $k=6$.  (a) $A$ (atas) dan  $C$ (bawah) setelah baris 6. (b) $C$ setelah baris 10. (c)-(e) Larik $B$ (atas) dan $C$ bawah) setelah satu, dua, dan tiga iterasi dari loop 14-15. (f) Larik $B$ setelah algoritma selesai dijalankan.}
\caption{Contoh eksekusi algoritme Counting-Sort.}
  \label{fig:counting-sort-illustration}
\end{figure}

Algoritma \textsc{Counting-Sort} diilustrasikan pada larik contoh
\(A\) dalam Gambar~\ref{fig:counting-sort-illustration}. Inisialisasi
pada baris 3 mengisi larik \(C\) dengan nilai 0. Nantinya larik \(C\)
ini akan digunakan untuk mencatat ada berapa bilangan di \(A\) yang
nilainya sama dengan indeks dari \(C\). Besarnya larik \(C\)
tergantung dari nilai terbesar yang ada dalam \(A\), dalam contoh ini
adalah \(k = 6\).

Pada baris 5-7, setiap nilai dalam \(A\) diperiksa, jika nilai dari
elemen tersebut adalah \(i\), maka nilai \(C[i]\) ditambahkan.
Sehingga setelah baris 5-7, larik \(C\) akan berisi jumlah elemen di
\(A\) yang sama dengan \(i\), untuk nilai-nilai \(i = 1, 2, \ldots,
k\). Pada Gambar~\ref{subfig:counting-sort-illustration-1}, elemen
ketiga dari \(C\) menyatakan bahwa ada 2 bilangan di \(A\) yang
nilainya 3.

Baris 9-11 menentukan untuk setiap \(i = 1, 2, \ldots, k\) berapa
banyak elemen di \(A\) yang nilainya lebih kecil dari atau sama dengan
\(i\), ini dicapai dengan menyimpan \emph{running sum} dari isi larik
\(C\). Gambar~\ref{subfig:counting-sort-illustration-2} menunjukkan
isi larik \(C\) setelah baris 9-11 dikerjakan.

Akhirnya pada baris 13-16 setiap elemen \(A[j]\) ditempatkan pada
posisi terurut di larik \(B\). \emph{Loop} ini menempatkan
elemen-elemen di \(A\) ke \(B\) mulai dari belakang.
Gambar~\ref{subfig:counting-sort-illustration-3} menunjukkan \(A[8]\)
diletakkan pada posisi \(B[7]\). Posisi ke-7 di larik \(B\) didapatkan
dari larik \(C\): ``Di manakah letak \(\mathbf{4} = A[8]\) dalam larik
\(B\)?'' Jawabannya dapat ditemukan pada \(C[\mathbf{4}]\): ``Elemen
\(A[8]\) harus diletakkan pada posisi \(B[C[4]]\).''

Seandainya semua elemen di \(A\) nilainya berbeda, maka isi larik
\(C\) akan saling berbeda sebelum memasuki baris 13. Jika demikian,
bilangan yang nilainya \(i\) di \(A\) akan ditempatkan pada posisi
\(C[i]\) di \(B\). Kenyataannya bisa jadi ada elemen yang nilainya
sama di \(A\), maka setiap kali elemen \(A[j]\) diletakkan di \(B\),
nilai \(C[A[j]]\) dikurangi 1. Ini akan membuat elemen berikut yang
nilainya sama dengan \(A[j]\), jika ada, ditempatkan pada posisi tepat
sebelum \(A[j]\) di \(B\).

Salah satu sifat penting dari \emph{counting sort} adalah
\emph{\textbf{stable}} \index{\emph{stable property}}: bilangan yang
nilainya sama dan muncul pada urutan yang sama pada larik masukan
urutannya di larik keluaran akan tetap sama. Sebagai contoh, pada
Gambar~\ref{fig:counting-sort-illustration}, bilangan 4 di \(A[3]\)
muncul lebih dahulu daripada bilangan 4 di \(A[6]\). Pada larik \(B\),
\(4_{A[3]}\) akan berada di depan \(4_{A[6]}\) juga.


\section{Radix Sort} \label{sect:radix-sort} \index{\emph{Radix
  sort}}

Algoritma \emph{\textbf{Radix sort}} pertama kali digunakan untuk
mengurutkan \emph{punched cards}~\cite{cormen}. Kartu-kartu tersebut
disusun dalam 80 kolom di mana pada masing-masing kolom setiap kartu
bisa dilubangi di satu dari 12 tempat. Mesin yang mengurutkan
kartu-kartu tersebut diprogram secara mekanis untuk mendistribusikan
kartu ke 12 kotak, tergantung dari lokasi mana pada kartu yang
dilubangi. Seorang operator akan mengumpulkan kartu-kartu tersebut
kotak demi kotak, sehingga kartu yang dilubangi pada lokasi pertama
akan berada di atas kartu-kartu yang dilubangi pada lokasi kedua, dan
seterusnya.

Bilangan desimal dapat dianggap seperti kartu-kartu di atas, dengan 10
tempat yang bisa dilubangi. Bilangan 0 sampai 9 dapat dianggap sebagai
sepuluh buah kartu dengan kartu pertama dilubangi pada lokasi pertama,
kartu kedua dilubangi pada lokasi kedua, dan seterusnya. Untuk
mengurutkan bilangan-bilangan (`kartu-kartu') ini, digunakan mesin
pengurut kartu seperti di atas yang mengelompokkan bilangan-bilangan
tersebut ke 10 kotak berbeda. Kotak pertama akan menyimpan kartu yang
dilubangi pada posisi pertama, dan seterusnya. Bila terdapat lebih
dari 10 bilangan yang hanya terdiri atas satu digit saja, maka akan
ada kotak yang diisi oleh bilangan yang sama (\emph{Pigeonhole
    principle}). Gambar~\ref{fig:radix-sort-card-illus} menunjukkan
proses pengurutan 15 bilangan.

\begin{figure}
{\par\centering
\scalebox{0.8}{
\noindent \subfigure[]{\includegraphics{radix-sort-card-illus-1}
  \label{subfig:radix-sort-card-illus-1}} %\goodgap
\subfigure[]{\includegraphics{radix-sort-card-illus-2}
  \label{subfig:radix-sort-card-illus-2}}
} \par}
\caption{Contoh pengurutan bilangan satu-digit dengan radix
  sort. \label{fig:radix-sort-card-illus}}
\end{figure}

\subsection{MSD Radix Sort \label{subsect:msd-radix-sort}} \index{MSD
  radix sort}

Secara intuitif, untuk mengurutkan bilangan bulat yang terdiri dari
\(d\) digit (misalkan 3 digit), dapat dilakukan dengan mengelompokkan
bilangan-bilangan tersebut berdasarkan digit paling kiri (\emph{the
    Most Significant Digit}, MSD). Semua bilangan yang nilainya 100-an
dimasukkan ke kotak pertama, bilangan yang nilainya 200-an masuk ke
kotak kedua, dan seterusnya. Lalu secara rekursif, bilangan-bilangan
dalam setiap kotak diurutkan dengan melihat digit kedua:
Bilangan-bilangan dalam kotak pertama (yaitu yang nilainya 100-an)
dipilah-pilah ke dalam sepuluh kotak yang lain. Dengan cara seperti
ini kotak yang dibutuhkan akan semakin besar bila bilangan yang
diurutkan digitnya makin panjang (lihat
    Latihan~\ref{sum:jumlah-kotak-msd-radix}).

\subsection{LSD Radix Sort \label{subsect:lsd-radix-sort}} \index{LSD
  radix sort}

Untuk mengurangi jumlah kotak yang diperlukan, \emph{radix sort} dapat
dilakukan dengan mengurutkan mulai dari digit paling kanan (\emph{the
    Least Significant Digit}, LSD) lebih dahulu. Dengan cara ini,
\emph{LSD radix sort} membutuhkan \(d\) iterasi, dengan setiap iterasi
hanya memerlukan 10 kotak. Pada akhir setiap iterasi,
bilangan-bilangan yang sudah dikelompokkan di dalam kotak dikumpulkan
kembali mulai dari kotak pertama, kotak kedua, dan seterusnya. Pada
iterasi berikutnya, proses pengelompokan ke dalam kotak dilakukan lagi
namun diterapkan pada digit di sebelah kiri dari iterasi sebelumnya.
Gambar~\ref{fig:radix-sort-illus} menunjukkan operasi pengurutan
bilangan 3-digit dalam 3 iterasi.

\begin{figure}
{\par\centering
  \begin{tabular}{cccccccc}
    329 & & 720 & & 720 & & 329 \\
    457 & & 355 & & 329 & & 355 \\
    657 & & 436 & & 436 & & 436 \\
    839 & \( \Rightarrow \)& 457 & \(\Rightarrow\) & 839 &
    \(\Rightarrow\) & 457 \\
    436 & & 657 & & 355 & & 657 \\
    720 & & 329 & & 457 & & 720 \\
    355 & & 839 & & 657 & & 839 \\
     & & \multicolumn{1}{r}{\( \uparrow \)}
      & & \multicolumn{1}{c}{\( \uparrow \)}
      & & \multicolumn{1}{l}{\( \uparrow \)} \\
  \end{tabular}
\par}
\caption{LSD Radix sort pada sekelompok bilangan 3-digit.}
  \label{fig:radix-sort-illus}
\end{figure}

Algoritma \emph{radix sort} cukup sederhana
(Algoritma~\ref{alg:radix-sort}). Algoritma tersebut menggunakan
asumsi setiap elemen di larik \(A\) tersusun atas \(d\) digit, dengan
digit 1 merupakan LSD dan digit \(d\) merupakan MSD.

\begin{algorithm}
\begin{algorithmic}[1]
  \STATE \textsc{Radix-Sort} \( (A, d) \)
  \FOR{ \(i \leftarrow 1\) to \(d\) }
    \STATE gunakan algoritma sorting yang \emph{stable} untuk
    mengurutkan \(A\) pada digit \(i\)
  \ENDFOR
\end{algorithmic}
\caption{Algoritma \textsc{Radix-Sort}. \label{alg:radix-sort}}
\end{algorithm}

\emph{Radix sort} kadang digunakan untuk mengurutkan \emph{records}
yang dibuat sedemikian rupa sehingga setiap \emph{record} memiliki
\emph{multiple key}. Contohnya adalah data tanggal, yang memiliki
kunci tahun, bulan, dan hari. Untuk mengurutkan data-data semacam ini,
\emph{radix sort} dapat digunakan dengan pertama kali mengurutkan
hari, kemudian bulan, dan terakhir tahun.


\section{Latihan \label{sect:sum-sorting}}

\begin{enumerate}

\item \label{sum:jumlah-kotak-msd-radix} Berapa jumlah kotak yang
dibutuhkan untuk mengurutkan bilangan heksadesimal yang tersusun atas
8-digit bila menggunakan \emph{MSD radix sort}?
\end{enumerate}

